package com.algorithm.动态规划;

/**
 * 给定一个长度为 n 的整数序列，求它的最大连续子序列和
 * 比如 –2、1、–3、4、–1、2、1、–5、4 的最大连续子序列和是 4 + (–1) + 2 + 1 = 6
 * 这道题也属于最大切片问题(最大区段，Greatest Slice)
 * <p>
 * 概念区分: 子串、子数组、子区间必须是连续的，子序列是可以不连续的
 */
public class 最大连续子序列和 {
    public static void main(String[] args) {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println(maxSubArray2(nums));
    }

    static int maxSubArray1(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        System.out.println("dp[0] = "+dp[0]);
        int max = dp[0];
        for (int i = 1; i < nums.length; i++) {
            if (dp[i - 1] < 0) {
                dp[i] = nums[i];
            } else {
                dp[i] = dp[i - 1] + nums[i];
            }
            System.out.println("dp[" + i +"] = " + dp[i]);
            max = Math.max(max, dp[i]);
        }
        return max;
    }

    static int maxSubArray2(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int dp = nums[0];
        System.out.println("dp[0] = "+dp);
        int max = dp;
        for (int i = 1; i < nums.length; i++) {
            if (dp < 0) {
                dp = nums[i];
            } else {
                dp = dp + nums[i];
            }
            System.out.println("dp[" + i +"] = " + dp);
            max = Math.max(max, dp);
        }
        return max;
    }
}
